#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <cstdio>
#include <string>
#include <stack>
#include <set>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;
ll a[105][105];
const ll INF=0x3f3f3f3f;

int main()
{
    IOS;
    ll n,m,x,y,c;
    while(cin>>n>>m&&(n||m)){
        memset(a,INF,sizeof(a));
        for(ll i=1;i<=n;i++)a[i][i]=0;
        for(ll i=0;i<m;i++){
            cin>>x>>y>>c;
            a[x][y]=a[y][x]=min(a[x][y],c);
        }
        for(ll i=1;i<=n;i++){
            for(ll j=1;j<=n;j++){
                for(ll k=1;k<=n;k++){
                    a[j][k]=min(a[j][k],a[j][i]+a[i][k]);
                }
            }
        }
        cout<<a[1][n]<<endl;
    }    
    getchar();
    getchar();
    return 0;
}
